/**
 * 
 */
package leetCode;

import java.util.Arrays;

/**
 * @author zhong
 *
 */
public class FriendsOfAppropriateAges {
	public int binarySearchFirst(int[] a, int fromIndex, int endInex, int t) {
		int left = fromIndex, right = endInex;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (a[mid] < t) {
				left = mid + 1;// 右移
			} else if (a[mid] > t) {
				right = mid - 1;// 左移
			} else {
				if (mid == 0 || a[mid - 1] != t) {
					return mid;
				} else {
					// 向左
					right = mid - 1;
				}
			}
		}
		return -1;
	}

	public int biSearchLast(int[] a, int fromIndex, int endInex, int t) {
		int left = fromIndex, right = endInex;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (a[mid] < t) {
				left = mid + 1;// 右移
			} else if (a[mid] > t) {
				right = mid - 1;// 左移
			} else {
				if (mid == a.length - 1 || a[mid + 1] != t) {
					return mid;
				} else {
					// 向右
					left = mid + 1;
				}
			}
		}
		return -1;
	}

	public int numFriendRequests(int[] ages) {
		int total = 0;
		Arrays.sort(ages);
		for (int i = 0; i < ages.length; i++) {
			int age = ages[i];
			int min = (int) Math.floor(0.5 * age + 8);// 下届的第一个
			int max = age + 1;// 上界的右侧第一个
			// if (min >= max)
			// continue;
			// int index1 = binarySearchFirst(ages, 0, ages.length - 1, min);
			// int index2 = biSearchLast(ages, i, ages.length - 1, age);
			int index1 = Arrays.binarySearch(ages, min);
			if (index1 < 0) {
				index1 = -index1 - 1;
			} else {
				while (index1 != 0 && ages[index1 - 1] == min) {
					index1--;
				}
			}

			int index2 = Arrays.binarySearch(ages, max);
			if (index2 < 0) {
				index2 = -index2 - 1;
			} else {
				while (index2 != 0 && ages[index2 - 1] == max) {
					index2--;
				}
			}

			System.out.println(i + " " + age + ":    " + min + ":" + index1 + " " + max + ":" + index2);
			System.out.println(index2 - index1 - 1);
			total += (Math.max(0, index2 - index1));
		}
		return total - ages.length;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] ages = { 45, 45, 41, 23, 99, 19, 90, 44, 24, 10, 24, 20, 78, 104, 91 };// { 45, 45, 41, 23, 99, 19, 90,
																						// 44, 24, 10, 24, 20, 78, 104,
																						// 91 };
		System.out.println(new FriendsOfAppropriateAges().numFriendRequests(ages));
	}

}
